package 算法练习;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;


/** 

* @author ：soulstones
* @version ：2019年9月15日 下午9:49:49 
* @Description：
* 
用非递归方式编码对一个二叉树的前、中、后、层次遍历。
*/
public class 非递归方法实现遍历二叉树 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] nodes = new int[n][2];
		for (int i = 0; i < n; i++) {
			nodes[i][0] = sc.nextInt();
			nodes[i][1] = sc.nextInt();
		}
		TreeNode1 root = getTreeNode(nodes, 0);
		preOrder(root);
		System.out.println("");
		inOrder(root);
		System.out.println("");
		postOrder(root);
		System.out.println("");
		levelOrder(root);
	}

	private static void levelOrder(TreeNode1 root) {
		Queue<TreeNode1> queue = new LinkedList<TreeNode1>();
		queue.add(root);
		while (!queue.isEmpty()) {
			TreeNode1 node = queue.poll();
			System.out.print(node.val + " ");
			if (node.left != null)
				queue.add(node.left);
			if (node.right != null)
				queue.add(node.right);
		}
	}

	private static void postOrder(TreeNode1 root) {
		Stack<TreeNode1> stack = new Stack<TreeNode1>();
		TreeNode1 p = root;
		TreeNode1 pre = null;
		while (p != null || !stack.isEmpty()) {
			if (p != null) {
				stack.push(p);
				p = p.left;

			} else {
				p = stack.peek();
				if (p.right == null || p.right == pre) {
					p = stack.pop();
					System.out.print(p.val + " ");
					pre = p;
					p = null;
				} else {
					p = p.right;
				}
			}
		}
	}

	private static void inOrder(TreeNode1 root) {
		Stack<TreeNode1> stack = new Stack<TreeNode1>();
		TreeNode1 p = root;
		while (p != null || !stack.isEmpty()) {
			if (p != null) {
				stack.push(p);
				p = p.left;
			} else {
				p = stack.pop();
				System.out.print(p.val + " ");
				p = p.right;
			}
		}
	}

	private static void preOrder(TreeNode1 root) {
		Stack<TreeNode1> stack = new Stack<TreeNode1>();
		TreeNode1 p = root;
		while (p != null || !stack.isEmpty()) {
			if (p != null) {
				System.out.print(p.val + " ");
				stack.push(p);
				p = p.left;
			} else {
				p = stack.pop();
				p = p.right;
			}
		}
	}

	public static TreeNode1 getTreeNode(int[][] nodes, int idx) {
		if (idx < 0)
			return null;
		TreeNode1 node = new TreeNode1(idx + 1);
		node.left = getTreeNode(nodes, nodes[idx][0] - 1);
		node.right = getTreeNode(nodes, nodes[idx][1] - 1);
		return node;
	}
}

class TreeNode1 {
	TreeNode1 left;
	TreeNode1 right;
	int val;

	TreeNode1(int val) {
		this.val = val;
	}
}
